/**
 * @param {number} n - 楼梯总阶数
 * @return {number} - 不同的爬法数量
 */
//因为每次只能跨最多2步，因此到n阶前，必然只有走一步到达的情况 和 走两步到达的情况，
//如果是走1步到的--> 那么从上一个地方来这里只能走1步，在原有的基础上 * 1
//如果是走2步到的--> 那么从上一个地方来这里也只能走2步(走一步就是上面的情况)，在原有的基础上 * 1
//f(n) = f(n-1) + f(n-2) n>=0
var climbStairs = function(n) {
    // 特殊情况：如果只有1或2阶，直接返回结果
    if(n <= 2) return n

    // 创建 dp 数组存储每个楼梯的爬法数
    let dp = new Array(n + 1);
    dp[0] = 0;      // 非必须，可省略
    dp[1] = 1;      // 只有一种爬法
    dp[2] = 2;      // 两种爬法：1+1 或 2

    // 从第 3 阶开始计算，每阶楼梯等于前两阶之和
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
};

// 示例测试
let n = 4;
console.log(climbStairs(n)); // 输出：5